#include <iostream>
#include <cstring>
#define maxSize 100
using namespace std;

int getPriority(const char ch) {
    switch (ch) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
            return 0;
        default:
            return -1;
    }
}

void infixToPrefix(char ch[],char s2[],int &top2) {
    char s1[maxSize];
    int i = strlen(ch) - 1, top1 = -1;
    while (i>=0) {
        // 处理数字
        if (ch[i] >= '0' && ch[i] <= '9' || ch[i] >= 'a' && ch[i] <= 'z') {
            s2[++top2] = ch[i--];
        }
        // 处理运算符
        else if (ch[i] == '+' || ch[i] == '-' || ch[i] == '*' || ch[i] == '/') {
            if (top1 == -1 || s1[top1] == ')'|| getPriority(ch[i]) >= getPriority(s1[top1])) {
                s1[++top1] = ch[i--];
            } else {
                s2[++top2] = s1[top1--];
            }
        }
        // 处理右括号
        else if (ch[i] == ')') {
            s1[++top1] = ch[i--];
        }
        // 处理左括号
        else if (ch[i] == '(') {
            while (s1[top1] != ')') {
                s2[++top2] = s1[top1--];
            }
            top1--;
            i--;
        }
        else {
            i--;
        }
    }
    while (top1 != -1) {
        s2[++top2] = s1[top1--];
    }
}

int main() {
    char ch[] = "1+5*(2-(5+8)/3)";
    char ch2[] = "a+b-a*((c+d)/e-f)+g";
    char preFix[maxSize];
    int top = -1;
    infixToPrefix(ch2,preFix,top);
    for (int i = top; i >= 0;i--) {
        cout << preFix[i] << " ";
    }
    cout << endl;
    return 0;
}